//
//  QueueFromStack.hpp
//  Queue
//
//  Created by chenyh on 2021/2/5.
//

#ifndef QueueFromStack_hpp
#define QueueFromStack_hpp

#include <iostream>
#include "Stack.hpp"
using namespace std;

template <typename DataType>
class QueueFromStack {
public:
    QueueFromStack(int size = 10)
    {
        s1 = new Stack<DataType>(size);
        s2 = new Stack<DataType>(size);
    }
    ~QueueFromStack()
    {
        s1->~Stack();
        s2->~Stack();
    }
    bool push(DataType data);
    DataType pop();
private:
    Stack<DataType> *s1,*s2; //执行入队的操作栈1/2
    int size;
};


template <typename DataType>
bool QueueFromStack<DataType>:: push(DataType data) {
    if (s2->isEmpty()) {
        return s1->push(data); //如果s2为空，则直接入队
    }
    else if (s1->eleNumber() < size-s2->eleNumber())
    {//如果 s2 不为空，s1 只能入队 size-s2->eleNumber 个元素
        return s1->push(data);
    }else
    {
        cout<<"队列满"<<endl;
        return false;
    }
}

template <typename DataType>
DataType QueueFromStack<DataType>:: pop() {
    DataType temp;
    if (!s2->isEmpty()) { //如果s2不为空，则s2直接出栈
        return s2->pop();
    }
    else
    {
        while (!s1->isEmpty() && s1->eleNumber()>1) {
            temp = s1->pop(); //倒入eleNumber-1个元素
            s2->push(temp);   //压入s2
        }
        return s1->pop(); //直接将s1中剩下的一个元素弹出
    }


}

#endif /* QueueFromStack_hpp */
